import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 二叉树的层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/
public class Code01_LevelOrderTraversal {
    // 不提交这个类
    public static class TreeNode {
        // 节点的值
        public int val;
        // 左子节点
        public TreeNode left;
        // 右子节点
        public TreeNode right;
    }

    // 提交时把方法名改为levelOrder，此方法为普通bfs，此题不推荐
    public static List<List<Integer>> levelOrder1(TreeNode root) {
        // 用于存储最终层序遍历结果，外层List中的每个内层List代表二叉树的一层节点的值
        List<List<Integer>> ans = new ArrayList<>();
        if (root!= null) {
            // 用于实现广度优先搜索（BFS）的队列，存放待处理的节点
            Queue<TreeNode> queue = new LinkedList<>();
            // 用于记录每个节点所在的层次
            HashMap<TreeNode, Integer> levels = new HashMap<>();
            // 将根节点加入队列
            queue.add(root);
            // 记录根节点的层次为0
            levels.put(root, 0);
            // 只要队列不为空，就继续循环处理节点
            while (!queue.isEmpty()) {
                // 取出队列头部的节点
                TreeNode cur = queue.poll();
                // 获取当前节点的层次
                int level = levels.get(cur);
                // 如果结果集ans中还没有对应层次的列表，则创建一个新的空列表并添加到ans中
                if (ans.size() == level) {
                    ans.add(new ArrayList<>());
                }
                // 将当前节点的值添加到对应层次的列表中
                ans.get(level).add(cur.val);
                // 如果当前节点的左子节点不为空
                if (cur.left!= null) {
                    // 将左子节点加入队列
                    queue.add(cur.left);
                    // 记录左子节点的层次，比当前节点层次多1
                    levels.put(cur.left, level + 1);
                }
                // 如果当前节点的右子节点不为空
                if (cur.right!= null) {
                    // 将右子节点加入队列
                    queue.add(cur.right);
                    // 记录右子节点的层次，比当前节点层次多1
                    levels.put(cur.right, level + 1);
                }
            }
        }
        // 返回层序遍历结果
        return ans;
    }

    // 如果测试数据量变大了就修改这个值
    public static int MAXN = 2001;
    public static TreeNode[] queue = new TreeNode[MAXN];
    public static int l, r;

    // 提交时把方法名改为levelOrder，此方法为每次处理一层的优化bfs，此题推荐
    public static List<List<Integer>> levelOrder2(TreeNode root) {
        // 用于存储最终层序遍历结果
        List<List<Integer>> ans = new ArrayList<>();
        if (root!= null) {
            // 初始化队列的头和尾指针
            l = r = 0;
            // 将根节点加入队列
            queue[r++] = root;
            // 只要队列里还有节点，就继续循环处理
            while (l < r) {
                // 确定当前层的节点数量
                int size = r - l;
                // 用于存储当前层节点的值
                ArrayList<Integer> list = new ArrayList<>();
                // 处理当前层的每个节点
                for (int i = 0; i < size; i++) {
                    // 取出队列头部的节点
                    TreeNode cur = queue[l++];
                    // 将当前节点的值添加到当前层的列表中
                    list.add(cur.val);
                    // 如果当前节点的左子节点不为空
                    if (cur.left!= null) {
                        // 将左子节点加入队列
                        queue[r++] = cur.left;
                    }
                    // 如果当前节点的右子节点不为空
                    if (cur.right!= null) {
                        // 将右子节点加入队列
                        queue[r++] = cur.right;
                    }
                }
                // 将当前层的节点值列表添加到结果集ans中
                ans.add(list);
            }
        }
        // 返回层序遍历结果
        return ans;
    }
}